Separating axes
Introduction The method of separating axes is a simple and often powerful tool for determining whether two convex sets intersect. The method is generally discussed in the context of convex polyhedra, although generalizations can be made for parametric and implicit surfaces with convex interior. Besides its simplicity, an attractive aspect of the method is its tendency to simplify dramatically when the type of objects is restricted; for instance, the separating axes test between a box and a plane reduces to just two dot products. While more efficient algorithms can be found in the case of general convex polyhedra, in specific cases such as boxes, triangles, and other simple shapes, adaptations of this algorithm are often very efficient. The exposition is divided into two parts: the theoretical background and foundation (the Background and Separating Axes sections), and the implementation (the Implementation and Case Studies sections). The former can be skipped by anyone only interested in the implementation specifics. Background Let B_1 and B_2 be two non-intersecting convex objects. Then there exists a line L such that the projections of B_1 and B_2 onto L are disjoint. Proof: let x_1 and x_2 be the closest points on the two objects, with x_1 \in B_1 and x_2 \in B_2 . Let L be the line through the two points. Consider the planes P_1 and P_2 , perpendicular to L , and passing through x_1 and x_2 respectively (if dealing with objects in 2d, replace planes with lines). Let the normals of the two planes point toward each other along L . Since x_1 is the closest point to x_2 and vice versa, the planes are tangent to B_1 and B_2 respectively. By convexity, this means that no point of B_1 is in front of P_1 , and no point of B_2 is in front of P_2 . Therefore, the projection of B_1 and B_2 onto L contains no points between the projections of x_1 and x_2 , which concludes the proof. Similarly, it's easy to see that if B_1 and B_2 intersect, then no line L exists; for a sketch of a proof of this, suppose that L does exist, take the interval along L on which the projections are disjoint, and construct a plane through its midpoint, with the normal along L . Then the two objects are on opposite sides of the plane, contradicting the assumption that they were intersecting. This is not terribly useful yet; we've shown that a separating axis L exists if and only if the two objects do not intersect, and we've shown a means of finding such a line -- but finding the points x_1 and x_2 is a different problem (see Lin-Canny, for instance). The next section narrows down the number of lines we need to consider. Separating Axes We discuss the method for triangle meshes in 3d, although the approach here can be readily generalized to polyhedra with arbitrary faces. It's easy to see that the translation of any separating axis is a separating axis itself; therefore, we only need to consider lines through the origin. Given two triangle meshes, we can begin by attempting to enumerate the potential separating axes. In the previous section, we alluded to our choice of L as a line that is perpendicular to the tangent planes at x_1 and x_2 . This arose from the definition of x_1 and x_2 as the closest points between B_1 and B_2 , since the gradient of distance to x_1 is, by definition, perpendicular to the tangent plane at x_1 . At this point, we discard the idea of finding the closest two points, but keep the idea of finding lines that are perpendicular to tangent planes. This brings up a problem with triangle meshes: the tangents are discontinuous at vertices and edges, and thus not well-defined. Keeping this in mind, we first start with the tangents that are well-defined: that is, triangle planes. Since we want to pick lines L that are perpendicular to tangent planes, this gives us triangle normals as one set of directions for potential separating axes. This leaves out edges -- and, by extension, vertices. To visualize why it is necessary to consider edges, take two cubes, pick an edge from each, and align the midpoints of the two edges in such a way as to make the edges reside in the same plane, and form a 90 degree angle to each other. The cubes are disjoint, but the face normals fail to provide a separating axis. Intuitively, we will want to consider pairs of edges, one from B_1 , and the other from B_2 , and come up with a function of the edge vectors that will return a separating axis whenever a separating axis exists, and is perpendicular to tangent planes at both edges.